package demo2;


/**
 * 合并两个有序链表
 * https://leetcode.cn/problems/merge-two-sorted-lists/
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        return dfs(list1,list2);
    }

    private ListNode dfs(ListNode l1, ListNode l2) {
        // 出口
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val <= l2.val) {
            l1.next = dfs(l1.next,l2);
            return l1;
        }else {
            l2.next = dfs(l1,l2.next);
            return l2;
        }
    }
}